Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

So, also lasst uns beginnen. Herzlich willkommen zur Informationstheorie.

Wir sind am Ende von Kapitel 3. Kapitel 3 war Kodierung zur Verdichtung, zur kompakten Darstellung von Nachrichten.

Wir haben zuerst die nächste gemacht. Fixe Quellenwortlänge auf variable Code-Wortlänge.

Fixed to variable. Dann haben wir das umgedreht in variable source Wortlänge, also variable Quellenwortlänge auf fixede Code-Wortlänge.

Und dann haben wir im letzten Abschnitt das, was eigentlich so die Story begonnen hat, nämlich mit Fixer Quellenwortlänge, Fixer Code-Wortlänge.

Und das Konzept dahinter, also block to block, muss ich eigentlich da sagen, Block-Kodierung.

Und das Konzept dahinter sind die typischen Sequenzen. Man hält Code-Worte nur frei für, oder muss man besser sagen, Code-Worte hält man vor, nur für typische Quellen-Symbol-Sequenzen, nicht für untypische.

Und wenn eine untypische Quellen-Symbol-Sequenz auftritt, dann sagt man, es ist ein Kotierversagen.

Typisch ist es, wenn die relative Häufigkeit für jedes Symbol, zumindest bei der gedächtnislosen Quelle ist das so einfach, sonst ist es ein bisschen komplizierter, machen wir aber nicht.

Also wenn die relative Häufigkeit in einer Sequenz für ein Symbol nahe genug an der Wahrscheinlichkeit ist.

Und diese Differenz zwischen relative Häufigkeit hier und Wahrscheinlichkeit in Betragenaum soll also kleiner gleich Epsilon mal der Wahrscheinlichkeit sein.

Für jedes Symbol. Diese Forderungen sind nicht unabhängig, sondern statistisch gebunden, eben darüber, dass die Summe der relativ Häufigkeiten und die Summe der Wahrscheinlichkeiten einsergeben muss.

Aber im Zweifelsstück sieht halt die stärkere Bedingung.

Okay, dann haben wir jetzt dieses Beispiel gemacht. Und damit haben wir gesehen, dass typische Sequenzen eine Wahrscheinlichkeit haben, die zwischen 2 hoch minus L mal der Entropie

und ein bisschen kleiner und 2 hoch minus L mal die Entropie und ein bisschen größer sind.

Das heißt typische Sequenzen sind nahezu alle gleich wahrscheinlich.

Und damit gibt es genau, sieht man auch hier sofort, 2 hoch L mal Havonix typische Sequenzen.

Also können Längen, typische Sequenzen der Länge L, genau durch L mal H bit kodiert werden.

Weil L mal H bit gibt 2 hoch L mal H Adressen für Codingwörter.

Und damit sehen wir, pro Kodesymbol braucht man genau Havonix Entropie Binärsymbole. Und dann sind wir wieder genau beim Quellenkodierungstheorien.

Das sind jetzt den ganz einfachen Zusammenhang. Aber natürlich ist die Mathematik dahinter nicht so einfach.

Man muss diese Sätze alle schön beweisen, was wir schon gemacht haben.

Das heißt, wir haben dann festgestellt, wie groß ist die Wahrscheinlichkeit, dass wir eine nicht typische Sequenz haben, dass wir der Codier versagen haben.

Und da haben wir also rumgenähert mit der Unionbound und allem möglichen Zeug.

Und sind dann zu dieser Gleichung gekommen hier da unten, dass das die Wahrscheinlichkeit ist für Codierversagen.

Nämlich, dass hier mit der Länge L der Quellenwörter die Wahrscheinlichkeit für Codierversagen nach Null geht.

Also wenn ich die Quellenwörter nur groß genug mache, dann kann die Wahrscheinlichkeit für Codierversagen beliebig klein gemacht werden.

Und dann haben wir die Zahl der typischen Quellensymbolsequenzen.

Und das ist natürlich jetzt genau das, was ich schon gesagt habe. Es ist also zwei hoch L mal H von X.

Aber ein bisschen weniger als untere Schranke und zwei hoch L mal H von X und ein bisschen mehr als obere Schranke.

Und ein bisschen mehr, da ist genau dieses Epsilon drin, wie wir also diese typische Sequenz definiert haben.

Verstanden? Diese Grenze.

Okay, haben wir alles bewiesen.

Gut, und damit können wir also das Quellencodierungstheorien aufstellen.

Nämlich, wir brauchen also eine Codewortlänge bezogen auf die Länge des Quellensymbols, die die Entropie ist,

umgerechnet auf das mc-wertige Alphabet, mal eins plus Epsilon, ein kleines bisschen mehr, klar.

Wobei dieses Epsilon eins größer als null.

Aber ich kann das Epsilon eins beliebig klein machen, wenn L groß genug wird.

Und gleichzeitig wird dabei auch die Wahrscheinlichkeit für Dekodierversorgung beliebig klein.

Und damit sehen wir, dass also für sehr lange Quellenwörter die Entropie wieder genau erreicht werden kann, je Quellensymbol.

Und wir haben auch bewiesen, es kann nicht existieren, wenn ich weniger als die Entropie bit pro Quellensymbol versuche.

Dann kann es nicht funktionieren. Es existiert kein solches Verfahren.

Und das war also der Abschluss vom letzten Mal.

Man fasst es auch zusammen unter dem Begriff Asymptotic Equipartition Property.

Also AEP heißt Asymptotic Equipartition, also equivalent gleich, ist im Englischen mit E geschrieben, darum AEP, Asymptotic Equipartition.

Das heißt, die typischen Sequenzen haben alle die gleiche Wahrscheinlichkeit, asymptotisch.

Und für L gegen unendlich, für lange Sequenzen von Quellenwörter treten nur noch solche typischen Sequenzen aus.

Das ist eine Folge des Gesetzes der großen Zahlen, haben wir bewiesen letztes Mal.

Und also wir haben, also die Wahrscheinlichkeit für nicht typische Sequenzen wird so gering, dass wir sie vernachlässigen können, wenn L gegen unendlich geht.